package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC712 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int minimumDeleteSum(String s1, String s2) {
            long sum = 0;
            for (char ch : s1.toCharArray()) sum += ch;
            for (char ch : s2.toCharArray()) sum += ch;

            int[][] dp = new int[s1.length() + 1][s2.length() + 1];
            //dp[i][j]==s1.charAt(i)==s2.charAt(j)?
            for (int i = 0; i < s1.length(); i++) {
                for (int j = 0; j < s2.length(); j++) {
                    if (s1.charAt(i) == s2.charAt(j)) {
                        dp[i + 1][j + 1] = dp[i][j] + s1.charAt(i) * 2;
                    } else {
                        dp[i + 1][j + 1] = Math.max(Math.max(dp[i + 1][j], dp[i][j + 1]), dp[i][j]);
                    }
                }
            }

            return (int) (sum - dp[s1.length()][s2.length()]);
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.minimumDeleteSum("delete", "leet"));
    }

    public static void main(String[] args) throws Exception {
        LC712 an = new LC712();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
